Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
In [5]:
let createNewRow lst = [ 1UL ] @ lst @ [ 1UL ]
let rec contracting (row:uint64[]) =
if row.Length = 1 then row.[0]
else
[0..(row.Length-2)]
|> List.map (fun i -> row.[i] + row.[i+1])
|> List.toArray
|> contracting
let rec expanding max (row:uint64[]) =
if row.Length > max then contracting row
else
[0..(row.Length-2)]
|> List.map (fun i -> row.[i] + row.[i+1])
|> createNewRow
|> List.toArray
|> expanding max
expanding 3 [| |]
Out[5]:
In [ ]: